package com.fanwei.afgorithm.code146;

import java.util.LinkedHashMap;

/**
 * 146. LRU 缓存机制
 * 考题： https://leetcode-cn.com/problems/lru-cache/
 * 笔记： https://labuladong.gitbook.io/algo/mu-lu-ye-1/mu-lu-ye-3/lru-suan-fa#yi-lru-suan-fa-miao-shu
 * @author fanwei
 */
public class LRUCache {
    //队列大小
    int cap;
    //实现一个既有hash获取值，也有链表的结构的缓存擦车
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        //假如没有这个值
        if (!cache.containsKey(key)){
            return -1;
        }
        //将key值变为最近使用
        updateLastest(key);
        //返回结果
        return cache.get(key);
    }

    public void put(int key, int value) {
        //情况1:如果有这个值就更新，并且升级最新版本
        if (cache.containsKey(key)){
            cache.put(key,value);
            updateLastest(key);
            return;
        }
        //情况2：判断cap是否最大，是最大要删除没使用key，在插入新的key并升级最新版本
        //cache不能在添加元素，先要删除
        if (cache.size() >= cap){
            //cache头结点是最没有用到的key
           int oldKey =  cache.keySet().iterator().next();
           cache.remove(oldKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, value);
    }

    /**
     * 更新最新版本
     * @param key
     */
    private void updateLastest(int key) {
        Integer result = cache.get(key);
        cache.remove(key);
        cache.put(key,result);
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */